#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include "mpi.h"
#include <sys/utsname.h>
#include <string.h>

#define TIME_DIFF(t1, t2)						\
  ((t2.tv_sec - t1.tv_sec) * 1000000 + (t2.tv_usec - t1.tv_usec))

#define N 1024

void usage(char * prog)
{
  printf("%s nb_iteration\n", prog);
}


void output_board(int *board, int n, int loop) {
  int i,j;
  //printf("loop %d\n", loop);
  for (i=1; i<n+1; i++) {
    for (j=1; j<n+1; j++) {
      if (board[i*(n+2)+j])
	putchar('X');
      else
	putchar('.');
    }
    putchar('\n');
  }
}

int main(int argc, char* argv[]) {
  int i, j, loop, num_alive, num_alive_global, maxloop, next, previous;
  struct timeval t1, t2;
  unsigned long time;

  MPI_Status status;
  int myid, nb_nodes;

  /* initialiser MPI */
  MPI_Init(&argc,&argv);
  
  /* récupérer le nombre de processus lancés */
  MPI_Comm_size(MPI_COMM_WORLD,&nb_nodes);

  /* récupérer son propre numéro */
  MPI_Comm_rank(MPI_COMM_WORLD,&myid);
 
  int board[(N+2)*(N+2)];
  int n = N;
  int nb_lignes = N/(nb_nodes-1) + 2;
  int nb_elements = nb_lignes * (N+2);
  int taille_tranche =  nb_elements - 2*(N+2);


  if (argc != 2){
    usage(argv[0]);
    return EXIT_FAILURE;
  }
  maxloop = atoi(argv[1]);
  num_alive = num_alive_global = 0;

  for (i = 0; i <= N+1; i++) {
    for (j = 0; j <= N+1; j++) {
      if (i == N/2 || j == N/2) {
	board[i+j*(N+2)] = 1;
	num_alive ++;
      }
      else
	board[i+j*(N+2)] = 0;
    }
  }

  gettimeofday(&t1,NULL);


  if (myid == 0) {

    for (i = 1; i < nb_nodes; i++) {
      
      previous = (i == 1) ? nb_nodes-1 : i-1;
      next = (i == nb_nodes-1) ? 1 : i+1;
      
      MPI_Send(&previous, 1, MPI_INT, i, 0, MPI_COMM_WORLD);	
      MPI_Send(&next, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
      MPI_Send(&nb_nodes, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
      MPI_Send(&n, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
      MPI_Send(&nb_lignes, 1, MPI_INT, i, 0, MPI_COMM_WORLD);      
      MPI_Send(&nb_elements, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
      MPI_Send(board+(i-1)*(taille_tranche), nb_elements, MPI_INT, i, 0, MPI_COMM_WORLD); 
    }

    for (i = 1; i < nb_nodes; i++) {
      //MPI_Recv(board+(i-1)*(taille_tranche) + (N+2), taille_tranche, MPI_INT, i, 3, MPI_COMM_WORLD, &status);
      MPI_Recv(&num_alive, 1, MPI_INT, i, 3, MPI_COMM_WORLD, &status);
      num_alive_global += num_alive;
    }

    //output_board(board, N, 0);
    //    printf("Nombre de cellules vivantes : %d\n", num_alive_global);

    gettimeofday(&t2,NULL);
    
    time = TIME_DIFF(t1,t2);
    printf("%.2f\n",(float)time/1000);
  }

  else {
    MPI_Status status;
    MPI_Request req1, req2;
    int previous = 0, next = 0;
    int nb_elements = 0, nb_lignes = 0, n = 0, nb_nodes = 0;
    int msg = -1;
    int num_alive;

    
    MPI_Recv(&previous, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
    MPI_Recv(&next, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
    MPI_Recv(&nb_nodes, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
    MPI_Recv(&n, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
    MPI_Recv(&nb_lignes, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
    MPI_Recv(&nb_elements, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
    
    int board[nb_elements];
    int num_neigh[nb_elements];
    memset(board, 0, nb_elements * sizeof(int));
    memset(num_neigh, 0, nb_elements * sizeof(int));

    MPI_Recv(board, nb_elements, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);

    //int taille_tranche =  nb_elements - 2*(N+2);
    int send_sup[n+2];
    int send_inf[n+2];
    memset(send_sup, 0, (n+2) * sizeof(int));
    memset(send_inf, 0, (n+2) * sizeof(int));
    
    for (loop = 0; loop < maxloop; loop++) {    

      num_alive = 0;

      //Recopie
      send_sup[0] = board[n+2] = board[(n+2)+n];
      send_sup[n+1] = board[(n+2)+(n+1)] = board[(n+2)+1];
      
      send_inf[0] = board[(nb_lignes-2)*(n+2)] = board[(nb_lignes-2)*(n+2)+n];           
      send_inf[n+1] = board[(nb_lignes-2)*(n+2)+(n+1)] = board[(nb_lignes-2)*(n+2)+1];   
      
      for (i = 1; i <= n; i++) {
	send_sup[i] = board[(n+2)+i];
	send_inf[i] = board[(nb_lignes-2)*(n+2)+i];  
      } 

      MPI_Isend(send_sup, n+2, MPI_INT, previous, 1, MPI_COMM_WORLD, &req1); 
      MPI_Isend(send_inf, n+2, MPI_INT, next, 2, MPI_COMM_WORLD, &req2); 

      MPI_Recv(board+(nb_lignes-1)*(n+2), n+2, MPI_INT, next, 1, MPI_COMM_WORLD, &status);
      MPI_Recv(board, n+2, MPI_INT, previous, 2, MPI_COMM_WORLD, &status); 


      //Copie des colonnes extérieures concernées par le noeud courant
      for (i = 1; i < nb_lignes-1; i++) {
	board[i*(n+2)] = board[i*(n+2)+n];     
	board[i*(n+2)+(n+1)] = board[i*(n+2)+1];
      }

      MPI_Wait(&req1, &status);
      MPI_Wait(&req2, &status);

      //Calcul du nombre de voisins vivants sur les bordures des
      //colonnes extérieures
      for (i = 1; i <= n; i++) {
	num_neigh[(n+2)+i] = board[(n+2)+(i+1)] + board[(n+2)+(i-1)] +
	  board[2*(n+2)+i] + board[i] +
	  board[2*(n+2)+(i+1)] + board[i-1] +
	  board[2*(n+2)+(i-1)] + board[i+1];

	num_neigh[(nb_lignes-2)*(n+2)+i] = board[(nb_lignes-2)*(n+2)+(i+1)] + board[(nb_lignes-2)*(n+2)+(i-1)] +
	  board[(nb_lignes-1)*(n+2)+i] + board[(nb_lignes-3)*(n+2)+i] +
	  board[(nb_lignes-1)*(n+2)+(i+1)] + board[(nb_lignes-3)*(n+2)+(i-1)] +
	  board[(nb_lignes-1)*(n+2)+(i-1)] + board[(nb_lignes-3)*(n+2)+(i+1)];
      }
         
      MPI_Isend(&msg, 1, MPI_INT, previous, 1, MPI_COMM_WORLD, &req1); 
      MPI_Isend(&msg, 1, MPI_INT, next, 2, MPI_COMM_WORLD, &req2); 
    
      MPI_Recv(&msg, 1, MPI_INT, next, 1, MPI_COMM_WORLD, &status);
      MPI_Recv(&msg, 1, MPI_INT, previous, 2, MPI_COMM_WORLD, &status);   
    
      //Calcul du nombre de voisins vivants à l'intérieur
      for (i = 2; i < nb_lignes-2; i++) {
	for (j = 1; j <= n; j++) {
	  num_neigh[i*(n+2)+j] = board[i*(n+2)+(j+1)] + board[i*(n+2)+(j-1)] +
	    board[(i+1)*(n+2)+j] + board[(i-1)*(n+2)+j] +
	    board[(i+1)*(n+2)+(j+1)] + board[(i-1)*(n+2)+(j-1)] +
	    board[(i+1)*(n+2)+(j-1)] + board[(i-1)*(n+2)+(j+1)];
	}
      } 
    
      MPI_Wait(&req1, &status);
      MPI_Wait(&req2, &status);


      //Algo jeu de la vie
      num_alive = 0;
      int i, j;
      for (i = 1; i <= nb_lignes-2; i++) {
	for (j = 1; j <= n; j++) {
	  if (num_neigh[i*(n+2)+j] < 2 || num_neigh[i*(n+2)+j] > 3) 
	    board[i*(n+2)+j] = 0;
	  else
	    if (num_neigh[i*(n+2)+j] == 3)
	      board[i*(n+2)+j] = 1;

	  if (board[i*(n+2)+j] == 1) {
	    num_alive ++;
	  }
	}
      }
    }
    
    //MPI_Send(board+(n+2), taille_tranche, MPI_INT, 0, 3, MPI_COMM_WORLD); 
    MPI_Send(&num_alive, 1, MPI_INT, 0, 3, MPI_COMM_WORLD);
    
  }
  
  MPI_Finalize();
  
  return EXIT_SUCCESS;
}
